package com.vincent.algorithms.sort;

import java.util.*;

/**
 * 冒泡排序  从尾部开始比较相邻的元素  若后面的小于前面的则交换位置 （前面位置的先有序） 若从头部开始则 后面位置的先有序
 *
 * 平均复杂度 O(n^2)
 * 最坏情况复杂度 (n-1)+(n-2)+....1 = n*(n-1)/2  记为：O(n^2)
 * 最好情况复杂度 n-1  记为O(N)
 * 空间复杂度 O(1)
 * 稳定性 稳定
 * 排序方式 内部排序
 * 在查找中 冒泡排序仅需要一次遍历就可以找出最大或最小的值
 * Created by yangwenchang on 2017/8/22.
 */
public class BubbleSort implements Sort {

//    @Override
    public <T> void sort(T[] array,Comparator<? super T> c) {
        boolean flag = false;
        int swapCount = 0;
        int compareCount = 0;
        for (int i=0;i<array.length&&!flag;i++){
//            添加监控标志位  如果未发生交换 表示数组内容已经是有序的了 可以直接退出 短路标志
            flag=true;
//            i = 0 & j>i 这里表示了使用的是 前面先有序的方式
            for (int j = array.length-1;j>i;j--){
                compareCount++;
                if (c.compare(array[j-1],array[j])>0){
//                  发生过位置互换
                    flag = false;
                    System.out.println("交换位置"+(j-1)+":"+array[j-1]+","+j+":"+array[j]);
                    swapCount++;
                    swap(array,j-1,j);
                }
            }

        }
        System.out.println("总计交换次数:"+swapCount);
        System.out.println("总计比对次数:"+compareCount);
    }

    public static  <T> void swap(T[] a,int i, int j){
        T x = a[i];
        a[i] = a[j];
        a[j] = x;
    }

    public static void main(String[] args) {
//         比较好的方式之一
        List<Integer> list = new ArrayList(Arrays.asList(4, 2, 16, 9, 3));

//         方式一
//          List list = new ArrayList();
//          list.add(1);
//          list.add(2);

//         方式二  这其实是返回的是ArrayList的匿名子类  即 "双大括号初始化"法
//          List list = new ArrayList<Integer>() {
//            {
//                add(1);
//                add(2);
//                add(3);
//            }
//        };

//        方式三 Arrays.asList 返回的是Arrays类的内部私有ArrayList类(和我们常用的ArrayList不是同一个)
//        是final类型的 继承了AbstractList 但并没有重写 add 和 remove方法 所有调用者两方法会报UnsupportedOperationException
//        普通的get set contains indexOf 是没问题的
//            List list = Arrays.asList(1, 2, 3, 4, 5);
//        System.out.println(list.get(1));


//        数组的初始化
//        方式一 动态初始化
//        声明
//        　　int[] a;
//        　　int b[];
//        创建数组对象
//        　　a = new int[4];
//        　　b = new int[5];

//        默认初始化：数组元素相当于对象的成员变量，默认值跟成员变量的规则一样。数字0，布尔false，char\u0000，引用：null；
//        　　for(int i=0;i<a.length;i++){
//        　　　　a[i] = i*12;
//        　　}
//        方式二  静态初始化
//        　　int c[] = {23,43,56,78};//长度：4，索引范围：[0,3]
//        　　nameClass[] c2 = {
//        　　　　　　　　　　　　new nameClass("联想"),
//        　　　　　　　　　　　　new nameClass("华硕"),
//        　　　　　　　　　　　　new nameClass("惠普"),
//        　　　　　　　　　　　　new nameClass("DELL"),
//        　　　　　　　　　　　　new nameClass("宏基"),
//　　　　　　　　　　　　};

        Integer[] arr = {1,2,3,4,5};
        System.out.println(Arrays.toString(arr));
        new BubbleSort().sort(arr,(x,y)->x-y);
        System.out.println(Arrays.toString(arr));
//        List<Integer> list1 = new ArrayList<Integer>(Arrays.asList(4, 2, 16, 9, 3));
//        Collections.sort(list1,(x,y)->y-x);
//        for (Integer i:list1) {
//            System.out.println(i);
//        }
    }
}
